package leetcode;

/**
 * @author Liangyaoyun
 */
public class leetCode198 {
    //num[n]=num[n-2]+...+num[0]
    public int rob(int[] nums) {
        int len= nums.length;
        int[] dp=new int[len];
        int[] res=new int[len];
        dp[0]=nums[0];
        res[0]=nums[0];
        if (len==1){
            return dp[0];
        }
        dp[1]=nums[1];
        res[1]=nums[1];
        if (len==2){
            return Math.max(dp[0],dp[1]);
        }
        res[2]=nums[2];
        for (int i = 2; i < nums.length; i++) {
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
            if (i==2){
                continue;
            }
            res[i]=Math.max(res[i-2]+nums[i],res[i-3]+nums[i]);
        }
        int result=0;
        result=Math.max(res[len-2],res[len-1]);
        return Math.max(dp[nums.length-1],result);
    }

    public static void main(String[] args) {
        int[] nums=new int[]{4,1,2,7,5,3,1};
        leetCode198 leetCode198=new leetCode198();
        System.out.println(leetCode198.rob(nums));
    }
}
//[15,2,13,17]
//{
//dp[0]=nums[0]
//dp[1]=max(nums[0],nums[1])
//}
//dp[3]=max(dp[1]+nums[3],dp[2])=32
//dp[2]=max(dp[0](15)+nums[2](13),dp[1])=28
//dp[1]=15